template <class ItemType>
Graph<ItemType>::Graph()
{
	nnodes = 0;
	maxsize = 15;
	noedge = 0;
	int j, i;
	for (i = 0; i < maxsize; i++)
		for (j = 0; j < maxsize; j++)
			adj[i][j] = noedge;
}

template <class ItemType>
void Graph<ItemType>::AddNode(ItemType label)
{
	nnodes++;
	labels[nnodes - 1] = label;
}

template <class ItemType>
void Graph<ItemType>::Print(ostream& out)
{
	if (nnodes == 0)
		out << "Graph is empty" << endl;
	else
	{
		out << "Node\t:\t\tEdge to (weight)\n";
		out << "----------------------------------------------\n";
		int j;
		for (int i = 0; i < nnodes; i++)
		{
			out << labels[i] << "\t\t:\t";

			for (j = 0; j < nnodes; j++)
			{
				if (adj[i][j] != noedge)
				{
					out << labels[j] << " (" << adj[i][j] << ")  ";
				}
			}
			out << endl;
		}
	}
}

template <class ItemType>
void Graph<ItemType>::AddEdge(ItemType label1, ItemType label2, int weight)
{
	adj[findLabel(label1)][findLabel(label2)] = weight;
}

template <class ItemType>
void Graph<ItemType>::ChangeEdgeWeight(ItemType label1, ItemType label2, int weight)
{
	adj[findLabel(label1)][findLabel(label2)] = weight;
}

template <class ItemType>
void Graph<ItemType>::DeleteEdge(ItemType label1, ItemType label2)
{
	adj[findLabel(label1)][findLabel(label2)] = noedge;
}

template <class ItemType>
int Graph<ItemType>::findLabel(ItemType label)
{
	for (int i = 0; i < maxsize; i++)
		if (labels[i] == label)
			return i;
}

template <class ItemType>
list<ItemType> Graph<ItemType>::Depth(ItemType label)
{
	list<ItemType> visited;
	MarkVisited(findLabel(label), visited);

	return visited;
}

template <class ItemType>
void Graph<ItemType>::MarkVisited(int node, list<ItemType> &visited, ItemType find)
{
	for(int i = 0; i < nnodes; i++)
		if (adj[node][i] != noedge)
			if (!BeenVisited(visited, labels[i]))
			{
				visited.push_back(labels[i]);
				if (labels[i] == find)
					return;
				MarkVisited(i, visited, find);
			}
}

template <class ItemType>
bool Graph<ItemType>::BeenVisited(list<ItemType> visited, ItemType node)
{
	while(!visited.empty())
		if(visited.front() == node)
			return true;
		else
			visited.pop_front();
	
	return false;
}

template <class ItemType>
list<ItemType> Graph<ItemType>::findPath(ItemType label1, ItemType label2)
{
	list<ItemType> visited;
	visited.push_back(label1);
	MarkVisited(findLabel(label1), visited, label2);

	return visited;
}

template <class ItemType>
void Graph<ItemType>::DeleteNode(ItemType label)
{
	int node = findLabel(label);
	for (int i = 0; i < nnodes; i++)
	{
		adj[node][i] = adj[nnodes - 1][i];
	}
	for (int i = 0; i < nnodes; i++)
	{
		adj[i][node] = adj[i][nnodes - 1];
	}
	labels[node] = labels[nnodes - 1];
	labels[nnodes - 1] = "";
	nnodes--;
}

template <class ItemType>
list<ItemType> Graph<ItemType>::Breadth(ItemType label)
{
	int node;
	queue<int> Q;
	list<ItemType> visited;

	visited.push_back(label);
	Q.push(findLabel(label));

	while(!Q.empty())
	{
		node = Q.front();
		Q.pop();
		for (int i = 0; i < nnodes; i++)
			if (adj[node][i] != noedge)
			{
				if (!BeenVisited(visited, labels[i]))
				{
					visited.push_back(labels[i]);
					Q.push(node);
				}
			}
	}
	return visited;
}

template <class ItemType>
bool Graph<ItemType>::isUndirected()
{
	for (int i = 0; i < nnodes; i++)
		for(int j = 0; j < nnodes; j++)
			if (adj[i][j] != noedge)
				if (adj[j][i] == noedge)
					return false;
	return true;
}

template <class ItemType>
void Graph<ItemType>::WithinN(int node, list<ItemType> &visited, int nEdges)
{
	for (int i = 0; i < nnodes; i++)
		if (adj[node][i] != noedge)
			if (!BeenVisited(visited, labels[i]))
			{
				if (nEdges == 0)
					return;
				visited.push_back(labels[i]);
				WithinN(i, visited, nEdges - 1);
			}
}

template <class ItemType>
list<ItemType> Graph<ItemType>::NodesWithinNEdges(ItemType label, int N)
{
	list<ItemType> visited;
	WithinN(findLabel(label), visited, N);
	return visited;
}

template <class ItemType>
void Graph<ItemType>::findNetworkFlow(Graph<ItemType> &flow)
{
	//not complete
}